home *** CD-ROM | disk | FTP | other *** search
/ Software of the Month Club 2000 October / Software of the Month - Ultimate Collection Shareware 277.iso / pc / PROGRAMS / UTILITY / WINLINUX / DATA1.CAB / programs_-_include / LINUX / GHASH.H < prev    next >
C/C++ Source or Header  |  1999-09-17  |  5KB  |  219 lines
  1. /*
  2.  * include/linux/ghash.h -- generic hashing with fuzzy retrieval
  3.  *
  4.  * (C) 1997 Thomas Schoebel-Theuer
  5.  *
  6.  * The algorithms implemented here seem to be a completely new invention,
  7.  * and I'll publish the fundamentals in a paper.
  8.  */
  9.  
  10. #ifndef _GHASH_H
  11. #define _GHASH_H
  12. /* HASHSIZE _must_ be a power of two!!! */
  13.  
  14.  
  15. #define DEF_HASH_FUZZY_STRUCTS(NAME,HASHSIZE,TYPE) \
  16. \
  17. struct NAME##_table {\
  18.     TYPE * hashtable[HASHSIZE];\
  19.     TYPE * sorted_list;\
  20.     int nr_entries;\
  21. };\
  22. \
  23. struct NAME##_ptrs {\
  24.     TYPE * next_hash;\
  25.     TYPE * prev_hash;\
  26.     TYPE * next_sorted;\
  27.     TYPE * prev_sorted;\
  28. };
  29.  
  30. #define DEF_HASH_FUZZY(LINKAGE,NAME,HASHSIZE,TYPE,PTRS,KEYTYPE,KEY,KEYCMP,KEYEQ,HASHFN)\
  31. \
  32. LINKAGE void insert_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\
  33. {\
  34.     int ix = HASHFN(elem->KEY);\
  35.     TYPE ** base = &tbl->hashtable[ix];\
  36.     TYPE * ptr = *base;\
  37.     TYPE * prev = NULL;\
  38. \
  39.     tbl->nr_entries++;\
  40.     while(ptr && KEYCMP(ptr->KEY, elem->KEY)) {\
  41.         base = &ptr->PTRS.next_hash;\
  42.         prev = ptr;\
  43.         ptr = *base;\
  44.     }\
  45.     elem->PTRS.next_hash = ptr;\
  46.     elem->PTRS.prev_hash = prev;\
  47.     if(ptr) {\
  48.         ptr->PTRS.prev_hash = elem;\
  49.     }\
  50.     *base = elem;\
  51. \
  52.     ptr = prev;\
  53.     if(!ptr) {\
  54.         ptr = tbl->sorted_list;\
  55.         prev = NULL;\
  56.     } else {\
  57.         prev = ptr->PTRS.prev_sorted;\
  58.     }\
  59.     while(ptr) {\
  60.         TYPE * next = ptr->PTRS.next_hash;\
  61.         if(next && KEYCMP(next->KEY, elem->KEY)) {\
  62.             prev = ptr;\
  63.             ptr = next;\
  64.         } else if(KEYCMP(ptr->KEY, elem->KEY)) {\
  65.             prev = ptr;\
  66.             ptr = ptr->PTRS.next_sorted;\
  67.         } else\
  68.             break;\
  69.     }\
  70.     elem->PTRS.next_sorted = ptr;\
  71.     elem->PTRS.prev_sorted = prev;\
  72.     if(ptr) {\
  73.         ptr->PTRS.prev_sorted = elem;\
  74.     }\
  75.     if(prev) {\
  76.         prev->PTRS.next_sorted = elem;\
  77.     } else {\
  78.         tbl->sorted_list = elem;\
  79.     }\
  80. }\
  81. \
  82. LINKAGE void remove_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\
  83. {\
  84.     TYPE * next = elem->PTRS.next_hash;\
  85.     TYPE * prev = elem->PTRS.prev_hash;\
  86. \
  87.     tbl->nr_entries--;\
  88.     if(next)\
  89.         next->PTRS.prev_hash = prev;\
  90.     if(prev)\
  91.         prev->PTRS.next_hash = next;\
  92.     else {\
  93.         int ix = HASHFN(elem->KEY);\
  94.         tbl->hashtable[ix] = next;\
  95.     }\
  96. \
  97.     next = elem->PTRS.next_sorted;\
  98.     prev = elem->PTRS.prev_sorted;\
  99.     if(next)\
  100.         next->PTRS.prev_sorted = prev;\
  101.     if(prev)\
  102.         prev->PTRS.next_sorted = next;\
  103.     else\
  104.         tbl->sorted_list = next;\
  105. }\
  106. \
  107. LINKAGE TYPE * find_##NAME##_hash(struct NAME##_table * tbl, KEYTYPE pos)\
  108. {\
  109.     int ix = hashfn(pos);\
  110.     TYPE * ptr = tbl->hashtable[ix];\
  111.     while(ptr && KEYCMP(ptr->KEY, pos))\
  112.         ptr = ptr->PTRS.next_hash;\
  113.     if(ptr && !KEYEQ(ptr->KEY, pos))\
  114.         ptr = NULL;\
  115.     return ptr;\
  116. }\
  117. \
  118. LINKAGE TYPE * find_##NAME##_hash_fuzzy(struct NAME##_table * tbl, KEYTYPE pos)\
  119. {\
  120.     int ix;\
  121.     int offset;\
  122.     TYPE * ptr;\
  123.     TYPE * next;\
  124. \
  125.     ptr = tbl->sorted_list;\
  126.     if(!ptr || KEYCMP(pos, ptr->KEY))\
  127.         return NULL;\
  128.     ix = HASHFN(pos);\
  129.     offset = HASHSIZE;\
  130.     do {\
  131.         offset >>= 1;\
  132.         next = tbl->hashtable[(ix+offset) & ((HASHSIZE)-1)];\
  133.         if(next && (KEYCMP(next->KEY, pos) || KEYEQ(next->KEY, pos))\
  134.            && KEYCMP(ptr->KEY, next->KEY))\
  135.             ptr = next;\
  136.     } while(offset);\
  137. \
  138.     for(;;) {\
  139.         next = ptr->PTRS.next_hash;\
  140.         if(next) {\
  141.             if(KEYCMP(next->KEY, pos)) {\
  142.                 ptr = next;\
  143.                 continue;\
  144.             }\
  145.         }\
  146.         next = ptr->PTRS.next_sorted;\
  147.         if(next && KEYCMP(next->KEY, pos)) {\
  148.             ptr = next;\
  149.             continue;\
  150.         }\
  151.         return ptr;\
  152.     }\
  153.     return NULL;\
  154. }
  155.  
  156. #define DEF_HASH_STRUCTS(NAME,HASHSIZE,TYPE) \
  157. \
  158. struct NAME##_table {\
  159.     TYPE * hashtable[HASHSIZE];\
  160.     int nr_entries;\
  161. };\
  162. \
  163. struct NAME##_ptrs {\
  164.     TYPE * next_hash;\
  165.     TYPE * prev_hash;\
  166. };
  167.  
  168. #define DEF_HASH(LINKAGE,NAME,HASHSIZE,TYPE,PTRS,KEYTYPE,KEY,KEYCMP,KEYEQ,HASHFN)\
  169. \
  170. LINKAGE void insert_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\
  171. {\
  172.     int ix = HASHFN(elem->KEY);\
  173.     TYPE ** base = &tbl->hashtable[ix];\
  174.     TYPE * ptr = *base;\
  175.     TYPE * prev = NULL;\
  176. \
  177.     tbl->nr_entries++;\
  178.     while(ptr && KEYCMP(ptr->KEY, elem->KEY)) {\
  179.         base = &ptr->PTRS.next_hash;\
  180.         prev = ptr;\
  181.         ptr = *base;\
  182.     }\
  183.     elem->PTRS.next_hash = ptr;\
  184.     elem->PTRS.prev_hash = prev;\
  185.     if(ptr) {\
  186.         ptr->PTRS.prev_hash = elem;\
  187.     }\
  188.     *base = elem;\
  189. }\
  190. \
  191. LINKAGE void remove_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\
  192. {\
  193.     TYPE * next = elem->PTRS.next_hash;\
  194.     TYPE * prev = elem->PTRS.prev_hash;\
  195. \
  196.     tbl->nr_entries--;\
  197.     if(next)\
  198.         next->PTRS.prev_hash = prev;\
  199.     if(prev)\
  200.         prev->PTRS.next_hash = next;\
  201.     else {\
  202.         int ix = HASHFN(elem->KEY);\
  203.         tbl->hashtable[ix] = next;\
  204.     }\
  205. }\
  206. \
  207. LINKAGE TYPE * find_##NAME##_hash(struct NAME##_table * tbl, KEYTYPE pos)\
  208. {\
  209.     int ix = hashfn(pos);\
  210.     TYPE * ptr = tbl->hashtable[ix];\
  211.     while(ptr && KEYCMP(ptr->KEY, pos))\
  212.         ptr = ptr->PTRS.next_hash;\
  213.     if(ptr && !KEYEQ(ptr->KEY, pos))\
  214.         ptr = NULL;\
  215.     return ptr;\
  216. }
  217.  
  218. #endif
  219.